//////
//////  AvaliableBinaryTreeByClass.cpp
//////  Tree
//////
//////  Created by Xavier on 2023/11/21.
//////
////
////#define ElemType char
////#include <stdio.h>
////#include <iostream>
////using namespace std;
////
////
////typedef struct BiNode{
////    ElemType data;
////    struct BiNode *lchild;//左孩子
////    struct BiNode *rchild;//右孩子
////    
////}BiNode, *BiTree;
////
//////创建二叉树
////void CreateBiTree(BiTree &T) {
////    ElemType ch;
////    cin >> ch;
////    if (ch == '#') T == NULL;
////    else {
////        T = new BiNode;
////        T->data = ch;
////        CreateBiTree(T->lchild);
////        CreateBiTree(T->rchild);
////    }
////}
////
//////前序遍历
////void PreOrderTraverse(BiTree T) {
////    if (T == NULL) {
////        return;
////    }
////    cout << T->data;
////    PreOrderTraverse(T->lchild);
////    PreOrderTraverse(T->rchild);
////    
////}
////
////int main (int argc, const char * argv[]) {
////    BiTree T;
////    CreateBiTree(T);
////    PreOrderTraverse(T);
////
////    
////}
//
//#include <stdio.h>
//#include <stdlib.h>
//#include <assert.h>
//
//typedef char BTDataType;
//
//typedef struct BinaryTreeNode
//{
//    struct BinaryTreeNode* left;
//    struct BinaryTreeNode* right;
//    BTDataType data;
//}BTNode;
//
//BTNode* BuyBTNode(BTDataType x)
//{
//    BTNode* node = (BTNode*)malloc(sizeof(BTNode));
//    if (node == NULL)
//    {
//        printf("malloc fail\n");
//        exit(-1);
//    }
//
//    node->data = x;
//    node->left = node->right = NULL;
//    return node;
//}
//
//BTNode* CreatBinaryTree()
//{
//    BTNode* node1 = BuyBTNode('A');
//    BTNode* node2 = BuyBTNode('B');
//    BTNode* node3 = BuyBTNode('C');
//    BTNode* node4 = BuyBTNode('D');
//    BTNode* node5 = BuyBTNode('E');
//    BTNode* node6 = BuyBTNode('F');
//
//    node1->left = node2;
//    node1->right= node3;
//    
//    node2->left = node4;
//    
//    node3->left = node5;
//    node3->right = node6;
//
//    return node1;
//}
//
//void PrevOrder(BTNode* root) {
//    if (root == NULL) {
//        printf("# ");
//        return;
//    }
//    printf("%c ", root->data);
//    PrevOrder(root->left);
//    PrevOrder(root->right);
//}
//
//void InOrder(BTNode* root) {
//    if (root == NULL){
//        printf("NULL ");
//        return;
//    }
//    InOrder(root->left);
//    printf("%d ", root->data);
//    InOrder(root->right);
//}
//
//// 后序 -- 自己实现，自己画图感受一下
//
//// 多次调用会有问题，没办法每次初始化为0
////int BTreeSize(BTNode* root)
////{
////    static int count = 0;
////    if (root == NULL)
////        return count;
////
////    ++count;
////    BTreeSize(root->left);
////    BTreeSize(root->right);
////
////    return count;
////}
//
//// 线程安全的问题，这个以后linux学了大家就知道了
////int count = 0;
////void BTreeSize(BTNode* root)
////{
////    if (root == NULL)
////        return;
////
////    ++count;
////    BTreeSize(root->left);
////    BTreeSize(root->right);
////}
//
//// 思想：遍历+计数
////void BTreeSize(BTNode* root, int* pCount)
////{
////    if (root == NULL)
////        return;
////
////    ++(*pCount);
////    BTreeSize(root->left, pCount);
////    BTreeSize(root->right, pCount);
////}
//
//int BTreeSize(BTNode* root) {
//    return root == NULL ? 0 :
//        BTreeSize(root->left)
//        + BTreeSize(root->right) + 1;
//}
//
//int BTreeLeafSize(BTNode* root)
//{
//    if (root == NULL)
//        return 0;
//
//    if (root->left == NULL && root->right == NULL)
//        return 1;
//
//    return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
//}
//
//// 第k层的节点的个数，k >= 1
//int BTreeKLevelSize(BTNode* root, int k)
//{
//    assert(k >= 1);
//
//    if (root == NULL)
//        return 0;
//
//    if (k == 1)
//        return 1;
//
//    return BTreeKLevelSize(root->left, k - 1)
//        + BTreeKLevelSize(root->right, k - 1);
//}
//
//int BTreeDepth(BTNode* root)
//{
//    if (root == NULL)
//        return 0;
//
//    int leftDepth = BTreeDepth(root->left);
//    int rightDepth = BTreeDepth(root->right);
//
//    return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
//}
//
//int main()
//{
//    BTNode* tree = CreatBinaryTree();
//    PrevOrder(tree);
//    printf("\n");
//
//    InOrder(tree);
//    printf("\n");
//
//    
//    /*printf("size:%d\n", BTreeSize(tree));
//    printf("size:%d\n", BTreeSize(tree));
//    printf("size:%d\n", BTreeSize(tree));*/
//
//    //count = 0;
//    //BTreeSize(tree);
//    //printf("size:%d\n", count);
//
//    //count = 0;
//    //BTreeSize(tree);
//    //printf("size:%d\n", count);
//
//    //count = 0;
//    //BTreeSize(tree);
//    //printf("size:%d\n", count);
//
//    /*int count1 = 0;
//    BTreeSize(tree, &count1);
//    printf("size:%d\n", count1);
//
//    int count2 = 0;
//    BTreeSize(tree, &count2);
//    printf("size:%d\n", count2);*/
//
//    printf("size:%d\n", BTreeSize(tree));
//    printf("size:%d\n", BTreeSize(tree));
//    printf("size:%d\n", BTreeSize(tree));
//
//    printf("Leaf size:%d\n", BTreeLeafSize(tree));
//
//    printf("Depth size:%d\n", BTreeDepth(tree));
//
//
//    return 0;
//}
